package com.sx.sx1.lintcode.day717;
import java.util.*;

public class LC248 {

    static class Solution {
        /**
         * @param a: An integer array
         * @param queries: The query list
         * @return: The number of element in the array that are smaller that the given integer
         */
        public List<Integer> countOfSmallerNumber(int[] a, int[] queries) {
            Map<Integer,Integer> set=  new HashMap<>(); //可能有重复的，因此用map,无重复的可以用Set
            for (int i : a) {
               if(!set.containsKey(i)){
                    set.put(i,0);
               }

               set.put(i,set.get(i)+1);
            }
            List<Integer> ans = new ArrayList<>();
            //建立线段树节点
            SegmentNode tree = buildTree(0,10000,set);
            for (int item : queries) {
                int x = queryless(tree,0,item-1);
                ans.add(x);
            }
            return ans;
        }

        public int queryless(SegmentNode node,int start,int end){
            if(start<=node.start && end>= node.end){
                return node.data;
            }
            int mid = node.start+((node.end-node.start)>>1);
            int left =0;
            int right =0;

            if(mid>=start){
                left = queryless(node.left,start,Math.min(end,mid));
            }

            if(mid<end){
                right = queryless(node.right,mid>=start? mid+1:start,end);
            }

            return left+right;
        }

        public SegmentNode buildTree(int start,int end, Map<Integer,Integer> set){
            if(start == end){
                SegmentNode node = new SegmentNode(start,end);
                if(set.containsKey(start)){
                    node.data=set.get(start);
                }
                return node;
            }

            SegmentNode root = new SegmentNode(start,end);
            int mid = start+((end-start) >>1 );
            root.left = buildTree(start,mid,set);
            root.right = buildTree(mid+1,end,set);
            root.data = root.left.data+root.right.data;
            return root;
        }
        static class SegmentNode{ //线段树节点
            public int start,end,data;
            public SegmentNode left,right;
            public SegmentNode(int s,int e){
                start = s;
                end =e;
            }
        }
    }


    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.countOfSmallerNumber(new int[]{1,2,7,8,5},new int[]{1,8,5}));
        System.out.println(obj.countOfSmallerNumber(new int[]{3,4,5,8},new int[]{2,4}));
        System.out.println(obj.countOfSmallerNumber(
                new int[]{55,81,56,91,35,92,10,53,27,94,64,45,19,44,52,19,79,12,16,90,97,33,73,2,20,68,19,7,17,62,45,48,62,26,85,4,63,67,56,16},
                new int[]{10,43,2,17,28,75,75,12}));
    }

}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有207条未读消息，请及时查看
248 · 统计比给定整数小的数的个数
算法
中等
通过率
25%

题目
题解23
笔记
讨论99+
排名
记录
描述
给定一个整数数组 （下标由 0 到 n-1，其中 n 表示数组的规模，数值范围由 0 到 10000），
以及一个 查询列表。对于每一个查询，将会给你一个整数，请你返回该数组中小于给定整数的元素的数量。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


在做此题前，最好先完成 线段树的构造 and 线段树查询 II 这两道题目。

样例
样例 1:

输入: array =[1,2,7,8,5] queries =[1,8,5]
输出:[0,4,2]
样例 2:

输入: array =[3,4,5,8] queries =[2,4]
输出:[0,1]
挑战
可否用一下三种方法完成以上题目。

仅用循环方法

分类搜索 和 二进制搜索

构建 线段树 和 搜索

相关知识
学习《 高级数据结构：线段树、树状数组》课程中的2.5线段树解决实战面试题1 Count of Smaller Number相关内容 ，了解更多相关知识！
标签
相关题目

249
统计前面比自己小的数的个数
困难

547
两数组的交集
简单

548
两数组的交集 II
简单
推荐课程

ACM金牌逐行带刷班
最适合懒人的刷题课--躺平看算法大神在线coding，讲解思路+现场debug，手撕面试高频题
236/1857
已开启智能提示
发起考试
30 分 00 秒
12345678910

控制台
        历史提交

 */

/*
[55,81,56,91,35,92,10,53,27,94,64,45,19,44,52,19,79,12,16,90,97,33,73,2,20,68,19,7,17,62,45,48,62,26,85,4,63,67,56,16]
[10,43,2,17,28,75,75,12]
输出数据
[3,13,0,6,11,26,26,4]
期望答案
[3,16,0,7,14,32,32,4]
 */
